package ArrayList;

/**
 * @Classname JZ17打印从1到最大的n位数
 * @Description TODO
 * @Date 2022/12/6 11:33
 * @Created by xjl
 */
public class JZ17打印从1到最大的n位数 {

    /**
     * @description 这个是暴力求解的结果
     * @param: n
     * @date: 2022/12/6 13:11
     * @return: int[]
     * @author: xjl
     */
    public int[] printNumbers(int n) {
        int[] array = new int[(int) (Math.pow(10, n) - 1)];
        for (int i = 0; i < array.length; i++) {
            array[i] = i + 1;
        }
        return array;
    }

    /**
     * @description 使用全排列的思想来实现
      * @param: null
     * @date: 2022/12/6 15:52
     * @return:
     * @author: xjl
    */
//    private StringBuilder num;
//    private int[] nums;
//    private int idx = 0, n;
//    private char[] chars = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
//
//    public int[] printNumbers2(int n) {
//        this.num = new StringBuilder();
//        this.nums = new int[(int) Math.pow(10, n) - 1];
//        this.n = n;
//        dfs(0);
//        return nums;
//    }
//
//    private void dfs(int i) {
//        if (i == n) {
//            int a = Integer.valueOf(num.toString());
//            if (a != 0) {
//                nums[idx++] = a; // 0 不计入结果
//            }
//            return;
//        }
//        for (char c : chars) {
//            num.append(c);
//            dfs(i + 1);
//            //  使用完成了 需要回溯刚刚取得的结果
//            num.deleteCharAt(num.length() - 1);
//        }
//    }

    // 若题目要求返回字符串形式的数字 String[] ，且存在大数，则可以另写一个 trim 方法去掉前置 0 。
    private StringBuilder num;
    private String[] nums;
    private int idx = 0, n;
    private char[] chars = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    public String[] printNumbers3(int n) {
        this.num = new StringBuilder();
        this.nums = new String[(int) Math.pow(10, n) - 1];
        this.n = n;
        dfs(0);
        return nums;
    }

    private void dfs(int i) {
        if (i == n) {
            StringBuilder tmp = new StringBuilder(num);
            // 如果是的返回的是string 类型，那就需要的在是否设置之前 将这个’0‘ 去掉
            String a = trim(tmp);
            if (a != "") {
                nums[idx++] = a;
            }
            return;
        }
        for (char c : chars) {
            num.append(c);
            dfs(i + 1);
            num.deleteCharAt(num.length() - 1);
        }
    }

    private String trim(StringBuilder num) {
        while (num.length() != 0 && num.charAt(0) == '0') {
            num.deleteCharAt(0);
        }
        return num.toString();
    }
}
